If the ordering is being screwed up, then your rotations are probably incorrect.
The delete must have several issues to produce that result. Don't worry about the delete for now though. Just focus on getting the insert correct first. Trying to get deletions correct when your tree is sometimes wrong to begin with, well just isn't going to happen.
What I find really useful with developing this sort of thing is to have something which verifies the tree at each step for me, so I can see exactly which operations screw it up. Here is the verification function I wrote for my red-black tree:
Code:
template <class TNode>
bool VerifyHelper(const TNode *head, int &numBlack) {
int numLeft=0, numRight=0;
if (head != NULL) {
if (head->left != NULL) {
if ((*head < *(head->left))
|| (head->red && head->left->red)
|| !VerifyHelper(head->left, numLeft)) return false;
}
if (head->right != NULL) {
if ((*(head->right) < *head)
|| (head->red && head->right->red)
|| !VerifyHelper(head->right, numRight)) return false;
}
if (numLeft != numRight) return false;
numBlack = numLeft + (head->red ? 0 : 1);
}
return true;
}
template <class TNode>
bool Verify(const TNode *head) {
int numBlack=0;
return (!red(head)) && VerifyHelper(head, numBlack);
}
This checks ordering, number of black nodes from root to each leaf, ensures there are no consecutive red nodes, and ensures the head is black - basically everything.
Your should be able to make whatever small modifications are needed to that to have it work with your code. Just call Verify with the head node and if it returns true you're good, and if it returns false, your tree is violating one of the properties I just listed.